// run: $exec < input
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

int const maxn = 100007;
int a[maxn];
int n;

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n;
		long long sum = 0;
		long long count = 0;
		for (int i = 0; i < n; i++) {
			long long x; std::cin >> x;
			if (x & 1)  { count++; x--; }
			sum += x;
		}
		if (!count) {
			std::cout << sum << "\n";
		} else {
			long long tmp = sum / count;
			if (tmp & 1) tmp--;
			std::cout << tmp + 1 << "\n";
		}
	}
}

